package Algorithm.search.others;

/**
 * LCR 069. 山脉数组的峰顶索引 https://leetcode.cn/problems/B1IidL/
 * 题目简述：求一个山峰数组（先严格递增后严格递减）的峰顶索引。
 */
public class PeakIndexInMountainArray {

    public static void main(String[] args) {
        new PeakIndexInMountainArray().peakIndexInMountainArray(new int[]{24,69,100,99,79,78,67,36,26,19});
    }
    /**
     * 思路：峰顶元素是在中间，故扫描[1, n-2]即可，定义[0,low)递增，(high,n-1]递减，二分比较扫描，最后low指向的就是结果
     */
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int low = 1, high = n - 2;
        while (low <= high) {
            int mid = low + high >> 1;
            if (arr[mid] < arr[mid+1])
                low = mid + 1;
            else high = mid - 1;
        }
        return low;
    }
}
